/*
    2. Write a C program to sort a list of elements using the selection sort algorithm. 
    According to Wikipedia “In computer science, selection sort is a sorting algorithm, 
    specifically an in-place comparison sort. It has O(n2) time complexity, making it 
    inefficient on large lists, and generally performs worse than the similar insertion 
    sort”.
    Note :
    a) To find maximum of elements
    b) To swap two elements
*/

#include <stdio.h>
#include <stdlib.h>

int findmaxindex(int a[], int len)
{
    int i;
    int max_index = 0;
    for(i = 1; i < len; i++){
        if(a[i] > a[max_index]){
            max_index = i;
        }
    }
    return max_index;
}

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void selectsort(int a[], int len)
{
    int i;
    int max_index;
    for(i = 0; i < len - 1; i++){
        max_index = findmaxindex(a, len - i);
        swap(&a[max_index], &a[len - 1 - i]);
    }
}

int main(void)
{
    int alen;
    int *a = NULL;
    int i;
    printf("Input the length of array : ");
    scanf("%d", &alen);
    a = (int *)malloc(alen * sizeof(int));
    printf("Input the element of array : \n");
    for(i = 0; i < alen; i++){
        scanf("%d", &a[i]);
    }
    selectsort(a, alen);
    printf("After selection sort : \n");
    for(i = 0; i < alen; i++){
        printf("%d, ", a[i]);
    }
    
    return 0;
}
